package top.minuy.structure.graph.representations.table;

import java.io.File;
import java.io.IOException;
import java.util.*;

/**
 * 正式在后面的例子中使用的图的表示类 简单图
 * 使用基于红黑树的邻接表实现
 * <p>
 * V1.1
 * 增加删除边功能
 * 增加深克隆功能
 * V1.2
 * 添加方向性
 * V1.3
 * 添加动态特性，顶点名改为字符串
 *
 * @author Minuy
 * @time 9:41
 * @date 2021/11/30
 */
public class GraphDynamic implements Cloneable {
    private int V; // 顶点个数
    private int E; // 边的条数
    private HashMap<String, HashSet<String>> adj; // 邻接矩阵
    private boolean isDirected; // 是否有向

    /**
     * 构造函数，构造一个图
     *
     * @param fileName 加载的文件名
     * @author Minuy
     * @date 2021/11/15 22:29
     */
    public GraphDynamic(String fileName) {
        this(fileName, false);
    }

    /**
     * 构造一个无向空图
     *
     * @author Minuy
     * @date 2021/11/30 10:00
     */
    public GraphDynamic() {
        this(null, false);
    }

    /**
     * 构造一个空图，并指定是否有向
     *
     * @param isDirected 是否有向
     * @author Minuy
     * @date 2021/11/30 10:00
     */
    public GraphDynamic(boolean isDirected) {
        this(null, isDirected);
    }

    public GraphDynamic(String fileName, boolean isDirected) {

        this.isDirected = isDirected;

        adj = new HashMap<>();

        if (fileName == null) {
            return;
        }

        File file = new File(fileName);

        // 这种语法可以不用手动关闭输入流
        try (Scanner scanner = new Scanner(file)) {
            int v = scanner.nextInt(); // 读入顶点数量
            if (0 > v) {
                // 顶点数量 必须是非负数的
                throw new IllegalArgumentException("V must be non-negative.");
            }
            // 创建邻接矩阵
            for (int i = 0; i < v; i++) {
                addVertex(i);
            }

            int e = scanner.nextInt(); // 读入边的数量
            if (0 > e) {
                // 边数量 必须是非负数的
                throw new IllegalArgumentException("E must be non-negative.");
            }

            for (int i = 0; i < e; i++) {
                int a = scanner.nextInt(); // 读入第一个顶点
                int b = scanner.nextInt(); // 读入第二个顶点

                addEdge(a, b);
            }
        } catch (IOException e) {
            e.printStackTrace();
        }
    }

    /**
     * 添加一个顶点
     *
     * @param v 顶点名
     * @author Minuy
     * @date 2021/11/30 9:45
     */
    public void addVertex(int v) {
        addVertex(String.valueOf(v));
    }

    /**
     * 添加一个顶点
     *
     * @param v 顶点名
     * @author Minuy
     * @date 2021/11/30 9:45
     */
    public void addVertex(String v) {
        adj.put(v, new HashSet<>());
        V++;
    }

    /**
     * 添加一条边
     *
     * @param v 起始顶点
     * @param w 结束顶点
     * @author Minuy
     * @date 2021/11/30 9:46
     */
    public void addEdge(int v, int w) {
        addEdge(String.valueOf(v), String.valueOf(w));
    }
/**
 * 添加一条边
 *
 * @param v 起始顶点
 * @param w 结束顶点
 * @author Minuy
 * @date 2021/11/30 10:21
 */
    public void addEdge(String v, int w) {
        addEdge(v, String.valueOf(w));
    }
    /**
     * 添加一条边
     *
     * @param v 起始顶点
     * @param w 结束顶点
     * @author Minuy
     * @date 2021/11/30 10:21
     */
    public void addEdge(int v, String w) {
        addEdge(String.valueOf(v), w);
    }

    /**
     * 添加一条边
     *
     * @param v 起始顶点
     * @param w 结束顶点
     * @author Minuy
     * @date 2021/11/30 10:01
     */
    public void addEdge(String v, String w) {
        if (hasEdge(v, w)) {
            throw new IllegalArgumentException(
                    String.format("Edge %s-%s is existent.", v, w));
        }

        if (v.equals(w)) {
            // 自环，不允许出现在简单图中
            throw new IllegalArgumentException("Self Loop is Detected.");
        }
        if (adj.get(v).contains(w)) {
            // 平行边，不允许出现在简单图中
            throw new IllegalArgumentException("Parallel Edges are Detected.");
        }

        // 连接两个顶点
        adj.get(v).add(w);

        if (!isDirected()) {
            adj.get(w).add(v); // 无向图的表示是两边都相连的
        }

        E++;
    }


    /**
     * 删除一个点
     * 返回值：
     * Map：out中是有向图被删除顶点的出边
     * Map：in中是有向图被删除顶点的入边
     * Map：edge中是无向图被删除顶点的邻边
     *
     * @param v 顶点id
     * @return Map<String, Set<String>> 被删除的顶点的出边和进边
     * @author Minuy
     * @date 2021/11/30 10:24
     */
    public Map<String, Set<String>> removeVertex(int v) {
        return removeVertex(String.valueOf(v));
    }

    /**
     * 删除一个点
     * 返回值：
     * Map：out中是有向图被删除顶点的出边
     * Map：in中是有向图被删除顶点的入边
     * Map：edge中是无向图被删除顶点的邻边
     *
     * @param v 顶点id
     * @return Map<String, Set<String>> 被删除的顶点的出边和进边
     * @author Minuy
     * @date 2021/11/30 10:43
     */
    public Map<String, Set<String>> removeVertex(String v) {
        validateVertex(v);
        Map<String, Set<String>> ret = new HashMap<>();
        Set<String> outEdge = adj.remove(v);

        if (isDirected()) {
            Set<String> inEdge = new HashSet<>();

            for (Map.Entry<String, HashSet<String>> w : adj.entrySet()) {
                for (String x : w.getValue()) {
                    if (x.equals(v)) {
                        inEdge.add(w.getKey());
                    }
                }
            }

            for (String w : inEdge) {
                adj.get(w).remove(v);
            }

            ret.put("out", outEdge);
            ret.put("in",inEdge);
        }else {
            for (String w : outEdge) {
                adj.get(w).remove(v);
            }
            ret.put("edge",outEdge);
        }
        return ret;
    }

    /**
     * 倒图， 针对于有向图
     *
     * @return Graph 倒图
     * @author Minuy
     * @date 2021/11/27 17:15
     */
    public GraphDynamic reverse() {

        if (!this.isDirected()) {
            throw new RuntimeException("The reverse only works in directed graph.");
        }

        try {
            GraphDynamic g = (GraphDynamic) super.clone();
            g.V = this.V;
            g.E = this.E;
            g.adj = new HashMap<>();
            g.isDirected = this.isDirected();

            for (Map.Entry<String, HashSet<String>> v : adj.entrySet()) {
                g.adj.put(v.getKey(), new HashSet<>());
            }

            for (Map.Entry<String, HashSet<String>> v : adj.entrySet()) {
                for (String w : v.getValue()) {
                    g.adj.get(w).add(v.getKey());
                }
            }

            return g;
        } catch (CloneNotSupportedException e) {
            e.printStackTrace();
        }
        return null;
    }

    /**
     * 验证顶点序号的合法性
     *
     * @param v 顶点值
     * @author Minuy
     * @date 2021/11/15 17:26
     */
    public void validateVertex(int v) {
        validateVertex(String.valueOf(v));
    }

    /**
     * 验证顶点名字的合法性
     *
     * @param v 顶点名字
     * @author Minuy
     * @date 2021/11/30 9:49
     */
    public void validateVertex(String v) {
        if (!adj.containsKey(v)) {
            throw new IllegalArgumentException("Vertex " + v + " is non-existent.");
        }
    }

    /**
     * 查询图是有向的还是无向的
     *
     * @return boolean 图的方向性
     * @author Minuy
     * @date 2021/11/27 9:07
     */
    public boolean isDirected() {
        return isDirected;
    }

    /**
     * 只读，边的数量
     *
     * @return int 边的数量
     * @author Minuy
     * @date 2021/11/15 17:35
     */
    public int E() {
        return E;
    }

    /**
     * 只读，顶点的数量
     *
     * @return int 顶点的数量
     * @author Minuy
     * @date 2021/11/15 17:35
     */
    public int V() {
        return V;
    }

    /**
     * 验证两个顶点之间是否有边
     *
     * @param v 顶点1的序号
     * @param w 顶点2的序号
     * @return boolean 有无边
     * @author Minuy
     * @date 2021/11/15 17:38
     */
    public boolean hasEdge(int v, int w) {
        return hasEdge(String.valueOf(v), String.valueOf(w));
    }

    /**
     * 验证两个顶点之间是否有边
     *
     * @param v 顶点1的序号
     * @param w 顶点2的序号
     * @return boolean 有无边
     * @author Minuy
     * @date 2021/11/30 10:20
     */
    public boolean hasEdge(String v, int w) {
        return hasEdge(v, String.valueOf(w));
    }
    /**
     * 验证两个顶点之间是否有边
     *
     * @param v 顶点1的序号
     * @param w 顶点2的序号
     * @return boolean 有无边
     * @author Minuy
     * @date 2021/11/30 10:20
     */
    public boolean hasEdge(int v, String w) {
        return hasEdge(String.valueOf(v), w);
    }
    /**
     * 验证两个顶点之间是否有边
     *
     * @param v 顶点1的名字
     * @param w 顶点2的名字
     * @return boolean 有无边
     * @author Minuy
     * @date 2021/11/30 9:57
     */
    public boolean hasEdge(String v, String w) {
        validateVertex(v);
        validateVertex(w);
        return adj.get(v).contains(w);
    }

    /**
     * 返回与顶点v相邻的所有顶点
     *
     * @param v 顶点v
     * @return Iterable<String> 与顶点v相邻的所有顶点
     * @author Minuy
     * @date 2021/11/15 19:55
     */
    public Iterable<String> adj(int v) {
        return adj(String.valueOf(v));
    }

    /**
     * 返回与顶点v相邻的所有顶点
     *
     * @param v 顶点v
     * @return Iterable<String> 与顶点v相邻的所有顶点
     * @author Minuy
     * @date 2021/11/30 10:04
     */
    public Iterable<String> adj(String v) {
        validateVertex(v);
        return adj.get(v);
    }

    /**
     * 获取顶点v的度
     *
     * @param v 顶点v
     * @return int 顶点v的度
     * @author Minuy
     * @date 2021/11/15 17:46
     */
    public int degree(int v) {
        // 对于有向图的度，分为出度和入度
        return degree(String.valueOf(v));
    }

    /**
     * 获取顶点v的度
     *
     * @param v 顶点v
     * @return int 顶点v的度
     * @author Minuy
     * @date 2021/11/30 10:05
     */
    public int degree(String v) {
        if (isDirected()) {
            throw new RuntimeException("The degree only works in undirected graph.");
        }
        validateVertex(v);
        return adj.get(v).size();
    }

    /**
     * 入度
     *
     * @param v 顶点v
     * @return int 入度
     * @author Minuy
     * @date 2021/11/27 10:05
     */
    public int indegree(int v) {
        return indegree(String.valueOf(v));
    }

    /**
     * 入度
     *
     * @param v 顶点v
     * @return int 入度
     * @author Minuy
     * @date 2021/11/30 10:09
     */
    public int indegree(String v) {
        if (!isDirected()) {
            throw new RuntimeException("The indegree only works in directed graph.");
        }
        validateVertex(v);
        int indegrees = 0;
        for (Map.Entry<String, HashSet<String>> w : adj.entrySet()) {
            for (String x : w.getValue()) {
                if (x.equals(v)) {
                    indegrees++;
                }
            }
        }
        return indegrees;
    }

    /**
     * 出度
     *
     * @param v 顶点v
     * @return int 出度
     * @author Minuy
     * @date 2021/11/27 10:05
     */
    public int outdegree(int v) {
        return outdegree(String.valueOf(v));
    }

    /**
     * 出度
     *
     * @param v 顶点v
     * @return int 出度
     * @author Minuy
     * @date 2021/11/30 10:10
     */
    public int outdegree(String v) {
        if (!isDirected()) {
            throw new RuntimeException("The outdegree only works in directed graph.");
        }
        validateVertex(v);
        return adj.get(v).size();
    }

    /**
     * 删除一条边
     *
     * @param v 顶点1
     * @param w 顶点2
     * @author Minuy
     * @date 2021/11/24 21:58
     */
    public void removeEdge(int v, int w) {
        removeEdge(String.valueOf(v), String.valueOf(w));
    }

    /**
     * 删除一条边
     *
     * @param v 顶点1
     * @param w 顶点2
     * @author Minuy
     * @date 2021/11/30 10:17
     */
    public void removeEdge(String v, int w) {
        removeEdge(v, String.valueOf(w));
    }
/**
 * 删除一条边
 *
 * @param v 顶点1
 * @param w 顶点2
 * @author Minuy
 * @date 2021/11/30 10:17
 */
    public void removeEdge(int v, String w) {
        removeEdge(String.valueOf(v),w);
    }


    /**
     * 删除一条边
     *
     * @param v 顶点1
     * @param w 顶点2
     * @author Minuy
     * @date 2021/11/30 10:16
     */
    public void removeEdge(String v, String w) {
        if (!hasEdge(v, w)) {
            throw new IllegalArgumentException(
                    String.format("Edge %s-%s is non-existent.", v, w));
        }

        adj.get(v).remove(w); // 删除边，不存在不会报错

        if (!isDirected()) { // 如果无向才删除“平行边”
            adj.get(w).remove(v);
        }

        E--;

    }

    /**
     * 深复制
     *
     * @return Graph 返回一个图
     * @author Minuy
     * @date 2021/11/24 22:05
     */
    @Override
    public GraphDynamic clone() {
        try {
            GraphDynamic g = (GraphDynamic) super.clone();
            g.V = this.V;
            g.E = this.E;
            g.adj = new HashMap<>();
            g.isDirected = this.isDirected();
            for (Map.Entry<String, HashSet<String>> v : adj.entrySet()) {
                g.adj.put(v.getKey(),new HashSet<>());
                for (String w : v.getValue()) {
                    g.adj.get(v.getKey()).add(w);
                }
            }
            return g;
        } catch (CloneNotSupportedException e) {
            e.printStackTrace();
        }
        return null;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append(String.format("V = %d, E = %d, isDirected = %s\n", V, E, isDirected));
        for (Map.Entry<String, HashSet<String>> v : adj.entrySet()) {
            sb.append(String.format("%s : ", v.getKey()));
            int i = 0;
            for (String w : v.getValue()) {
                sb.append(String.format("%s", w));
                if (i != v.getValue().size() - 1) {
                    sb.append(", ");
                }
                i++;
            }
            sb.append("\n");

        }
        return sb.toString();
    }
}
